#include"LinkStack.h"
#include"LinkQueue.h"
#include<iostream>

// 快速排序的非递归实现

// int main(int argc,char *argv[])
// {

    // // 进制转换器
    // LinkStack s;

    // int num = std::atoi(argv[1]);

    // int n = std::atoi(argv[2]);

    // while(num !=0)
    // {
    //     s.Push((void*)(long)(num % n));
    //     num /= n;
    //  }


    // while(!s.IsEmpty())
    // {
    //     long number = (long)*s.GetTop();

    //     if(number <= 9)
    //         std::cout<<number;
    //     else
    //         std::cout << (char)(number - 10 + 'a');

    //     s.Pop();
    // }

    // std::cout<<std::endl;









    // for(long i=0;i<10;i++)
    // {
    //     s.Push( (void *)(i+1) );
    // }

    // while(!s.IsEmpty())
    // {
    //     std::cout<<(long)*s.GetTop()<<" ";
        
    //     s.Pop();
    // }
    // std::cout<<std::endl;





int Partition(int *a ,int start, int end)
{
    int left = start;
    int right = end;

    int temp = a[left];

    while( left < right )
    {
        while(a[right]>temp  && left < right)
                    right--;
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }

        while(a[left]<temp && left<right)
                    left++;
        if(left < right)
        {
            a[right] = a[left];
            right--;
        }
        
    }
    a[left] = temp; 
    
    return left;
}

void Fast_No_Recur(int *a,int start,int end)
{
    LinkStack s;
    // 把区间的下表 入栈
    s.Push((void*)(long)start);
    s.Push((void*)(long)end);
    
    while(!s.IsEmpty())
    {                                            
        // 拿出区间
        long right = (long)*s.GetTop();
        s.Pop();
        long left = (long)*s.GetTop();
        s.Pop();
   

        long mid = Partition(a,left,right);
    
        if(left < mid-1)
        {
            s.Push((void*)(long)left);
            s.Push((void*)(long)(mid-1));
        }


        if(mid+1 < right)
        {
            s.Push((void*)(long)(mid+1));
            s.Push((void*)(long)right);
        }

    }


}


// int main()
// {
//     int a[] = {5,4,9,7,2,1,3};
   
//     Fast_No_Recur(a,0,6);
   
//     for(int i=0;i < 7;i++)
//     {
//         std::cout<<a[i]<<" ";
//     }
//     std::cout<<std::endl;


//     return 0;
// }





// int main()
// {
//     LinkQueue q;
//     for(int i=0;i<10;i++)
//     {
//         q.Push((void*)(long)(i+1));
//     }

//     while(!q.IsEmpty())
//     {
//         std::cout<<(long)*q.GetFront()<<" ";
//         q.Pop();
//     }
//     std::cout<<std::endl;


//     return 0;

// }
   
   
   
   
    // 约瑟夫环

int main()
{
    LinkQueue q;
    int count = 0;
    for(int i = 0;i<31;i++)
    {
        q.Push((void*)(long)(i+1));
    }
    while(q.Size() > 1)
    {
        long number = (long)*q.GetFront();
        q.Pop();
        count++;
        if(count!=3)
            q.Push((void*)(number));  
        else
           { std::cout<<number<<"出局\n";
             count = 0;
           } 
    }
    std::cout<<(long)*q.GetFront()<<"活了下来!"<<std::endl;


    return 0;

}